/**
 * 
 */
package br.com.grafos;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Classe principal que possui a implementação base do algoritmo de Dijkstra que
 * soluciona o problema do caminho mais curto num grafo
 * 
 * @author moises
 */
public class Dijkstra {

    /**
     * Método que constrói os caminhos do grafo a partir do nodo raíz
     * 
     * @param fonte
     *            - vértice raíz do grafo
     */
    public static void construirCaminhos(Vertice fonte) {
	// custo até ele próprio
	fonte.setMenorCusto(0);
	// inicializa fila de prioridades que conterá os vértices do grafo
	PriorityQueue<Vertice> fila = new PriorityQueue<Vertice>();
	// adiciona o raíz na fila
	fila.add(fonte);

	// laço que executa enquanto fila não estiver vazia
	while (!fila.isEmpty()) {
	    // remove e recupera nodo da fila
	    Vertice emissor = fila.poll();

	    // Visita todos vizinhos do nodo
	    for (Arco arco : emissor.getVizinhos()) {
		// recupera o nodo vizinho
		Vertice vizinho = arco.getDestino();
		// pega o custo associado
		int custo = arco.getCusto();
		// procura a menor distância desde o nodo raíz
		int distancia = emissor.getMenorCusto() + custo;
		// caso a distância seja menor
		if (distancia < vizinho.getMenorCusto()) {
		    // remove da fila, caso esteja presente
		    fila.remove(vizinho);
		    // seta o menor custo desde o nodo raíz
		    vizinho.setMenorCusto(distancia);
		    // seta o nodo emissor como antecessor do vizinho
		    vizinho.setAntecessor(emissor);
		    // adiciona vizinho na fila para verificação futura dos
		    // vizinhos do adjacente
		    fila.add(vizinho);
		}
	    }
	}
    }

    /**
     * Monta o caminho percorrido desde um vértice até o nodo anti raíz
     * 
     * @param nodo
     *            - nodo anti raíz
     * 
     * @return lista ordenada dos nodos percorridos do início ao fim
     */
    public static List<Vertice> buscarMenorCaminho(Vertice nodo) {
	List<Vertice> caminho = new ArrayList<Vertice>();
	// percorre os nodos até chegar no vértice raíz
	for (Vertice vertice = nodo; vertice != null; vertice = vertice
		.getAntecessor()) {
	    caminho.add(vertice);
	}

	// inverte a ordem dos elementos da lista
	Collections.reverse(caminho);
	return caminho;
    }

    /**
     * Mátodo de execução principal do programa
     * 
     * @param args
     */
    public static void main(String[] args) throws IOException {

	// chama processo de construção do grafo
	Grafo grafo = new FabricaGrafo().construir(args[0]);

	construirCaminhos(grafo.getRaiz());
	// imprime o custo do menor caminho
	System.out.println("Custo do caminho mais curto = "
		+ grafo.getAntiRaiz().getMenorCusto());

	// chama o método que calcula o menor caminho partindo do nodo raíz até
	// o nodo anti raíz
	List<Vertice> path = buscarMenorCaminho(grafo.getAntiRaiz());
	// imprime o caminho percorrido
	System.out.println("Caminho: " + path);
    }

}
